package 算法.十大排序算法;

import java.util.Arrays;

/**
 * @author coderFu
 * @create 2022/3/18
 * 归并排序
 * 先分， 后合并排序
 * 本质就是先将一个数组的两侧排序好，然后使用双指针移动，
 * 将后续的内容排序好
 */
public class CoderMergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,5,2,7};

        //sort(arr);
        int[] ints = sortByPoint(arr);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] sortByPoint(int[] arr){
        int[] array = new int[arr.length];
        int t = 0;
        int left = 0;
        int right = arr.length-1;
        int mid = left+(right-left)/2;
        int j = mid+1;
        while(left<=mid && j<= right){
            if (arr[left] < arr[j]){
                array[t++] = arr[left++];
            }else {
                array[t++] = arr[j++];
            }
        }
        // 左右两侧是否有剩余
        while (left<=mid){
            array[t++] = arr[left++];
        }

        while (j<=right){
            array[t++] = arr[j++];
        }
        return array;

    }

    public static int[] sort(int[] arr){
        // 建立一个等长的临时数组
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length-1,temp);
        return arr;
    }

    public static void  mergeSort(int[] arr, int left, int right,int[] temp){
        if (left < right){
            int mid = left + (right-left)/2;
            // 进行分离
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            // 进行合并
            merger(arr,left,mid,right,temp);
        }
    }
    public static void merger(int[] arr,int left, int mid, int right,int[] temp){
        // 左序列指针
        int i = left;
        // 右序列指针
        int j = mid+1;
        // 临时数组指针
        int t = 0;
        while(i<=mid && j<=right){
            if(arr[i] < arr[j]){
                temp[t++] = arr[i++];
            }else{
                temp[t++] = arr[j++];
            }
        }

        // 如果左边有剩余
        while(i<=mid){
            temp[t++] = arr[i++];
        }

        // 如果右边有剩余
        while(j<=right){
            temp[t++] = arr[j++];
        }

        t = 0;
        // 将临时数据还原到原数组中, 就会导致，在最后排序的时候
        //原数组的中间两边已经是有序的了，只要进行合并就可以。
        //双指针逼近排序。
        while(left <=right){
            arr[left++] = temp[t++];
        }
    }
}
